package baseclass.d_list;

import java.util.Random;
import java.util.concurrent.CountDownLatch;

/**
 * 使用抛硬币来提高链表高度的  跳表算法
 *
 * @date 2020/3/14 11:16
 */
public class SkipList2 {
    private static final byte HEAD_NODE = -1;
    private static final byte DATA_NODE = -1;
    private static final byte TAIL_NODE = -1;

    static class Node {
        int val;
        Node left, right, up, down;
        byte type;

        public Node(int val) {
            this(val, DATA_NODE);
        }

        public Node(int val, byte type) {
            this.val = val;
            this.type = type;
        }
    }

    Node head, tail;
    private final int capacity;
    private final int MAX_LEVEL;
    private int size;
    private int level;
    private Random random;

    public SkipList2(int capacity) {
        this.capacity = capacity;
        this.MAX_LEVEL = (int) (Math.log(capacity) / Math.log(2) + 1);
        head = new Node(Integer.MIN_VALUE, HEAD_NODE);
        tail = new Node(Integer.MAX_VALUE, TAIL_NODE);
        head.right = tail;
        tail.left = head;
        size = 0;
        level = 1;
        random = new Random(System.currentTimeMillis());
    }

    private Node findItSelfOrNear(int val) {
        Node node = head;
        //一层一层找
        for (; ; ) {
            while (node.right.type != TAIL_NODE && val >= node.right.val) {
                node = node.right;
            }
            if (node.down != null) {
                node = node.down;
            } else {
                break;
            }
        }

        return node;
    }
    public void add(int element){
        Node pre = findItSelfOrNear(element);
        Node newNode = new Node(element);
        newNode.left = pre;
        newNode.right = pre.right;
        pre.left = newNode;
        pre.right.left = newNode;
        addLevel(pre,newNode);
        size++;
    }

    private void addLevel(Node pre, Node node) {
        int targetLevel = getRandomLevel();
        int nextLevel = 2;
        while (nextLevel <= targetLevel){
            if(nextLevel > level){
                level++;
                Node newHead = new Node(Integer.MIN_VALUE,HEAD_NODE);
                Node newTail = new Node(Integer.MIN_VALUE,HEAD_NODE);
                newHead.right = newTail;
                newHead.down = head;
                head.up = newHead;
                newTail.left = newHead;
                newTail.down = tail;
                tail.up = newTail;
                head = newHead;
                tail = newTail;
            }
            while (pre != null && pre.up ==null) pre = pre.left;
            Node up = new Node(node.val);
            node.up = up;
            up.down = node;
            //把当前up和pre以及pre.right连接
            up.left = pre;
            up.right = pre.right;
            pre.right = up;
            pre.right.left = up;
            //更新node为up
            node = up;
            //更新下一个层级
            nextLevel++;
        }
    }

    public Integer delete(int element){
        Node node = findItSelfOrNear(element);
        if(node.val == element){
            doDelete(node);
            size--;
        }
        return null;
    }

    private void doDelete(Node node) {
        Node up,pre,next;
        do {
            up = node.up;
            pre = node.left;
            next = node.right;
            pre.right = next;
            next.left = pre;
            //help gc
            node.left = node.right = node.up = node.down = null;
            node = up;
        }while (up != null);
        //检测是否有一行只有head和tail
        while (level > 1 && pre.left == tail){
            // 删除head和tail
            pre = head.down;
            next = tail.down;
            head.left = head.right = head.up = head.down = null;
            tail.left = tail.right = tail.up = tail.down = null;
            head = pre;
            tail = next;
            level --;
        }
    }

    public int getRandomLevel(){
        int nextLevel = 1;
        while ((random.nextInt() & 1) == 0)
            nextLevel ++;
        return nextLevel >= MAX_LEVEL ? MAX_LEVEL :nextLevel;
    }

    public int size() {
        return size;
    }
    public void printSkipList() {
        System.out.println("size = " + size);
        Node temp = head;
        int curHeight = level;
        //遍历每一层
        while (temp != null) {
            System.out.printf("total level[%d]  current level [%d]", level, curHeight--);
            Node node = temp.right;
            while (node.type != TAIL_NODE) {
                System.out.print(" " + node.val + " ");
                node = node.right;
            }
            temp = temp.down;
            System.out.println();
        }
        System.out.println("===============");
    }

    public static void main(String[] args) throws InterruptedException {
        int MAX_VAL = 3;
        SkipList skipList = new SkipList(MAX_VAL);
        for (int i = 1; i <= MAX_VAL; i++) {
            skipList.add(i);
        }
        skipList.printSkipList();
        System.out.println(skipList.contains(0));
        System.out.println(skipList.contains(20));
        /*Node right = skipList.head.right;
        skipList.delete(right.val);
        skipList.printSkipList();*/
        for (int i = MAX_VAL; i >= 2; i--) {
            skipList.delete(i);
            skipList.printSkipList();
        }
/*        skipList.delete(13);
        skipList.printSkipList();
        skipList.delete(15);
        skipList.printSkipList();*/
    }



}
